package cn.bellychang.leetcode.question021;

/**
 * @author ChangLiang
 * @date 2021/1/28
 */
public class Solution2 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head = null;
        ListNode tail = null;

        // 循环不变量 一个一个连接起来
        while (l1 != null && l2 != null) {

            // 创建一个新的链表
            ListNode temp = new ListNode();

            if (l1.val <= l2.val) {
                temp.val = l1.val;
                l1 = l1.next;
            } else {
                temp.val = l2.val;
                l2 = l2.next;
            }
            if (head == null) {
                head = temp;
                tail = temp;
            } else {
                ListNode t = tail;
                tail = temp;
                t.next = tail;
            }
        }
        // 有一个为空了 那就将之后的连接起来
        // 如果两个都为空 什么都不做
        // 要注意head==null的情况
        if (l1 == null && l2 != null) {
            if (head == null) {
                head = l2;
            } else {
                ListNode t = tail;
                tail = l2;
                t.next = tail;
            }
        } else if (l2 == null && l1 != null) {
            if (head == null) {
                head = l1;
            } else {
                ListNode t = tail;
                tail = l1;
                t.next = tail;
            }
        }
        return head;
    }
}
